﻿#ifndef _BINTREE_H_
#define _BINTREE_H_
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode * Position;
typedef Position BinTree;
struct TNode
{
	ElementType Data;
	BinTree Left;			//这里用position好像也是一样的
	BinTree Right;
};

typedef struct TreeList * TList, *TStack;	//数据为树节点，指针域指向下一个	//定义一个堆栈
struct TreeList{
	BinTree Tree;
	TList Next;
};		

//===========================
//堆栈的操作

TStack initTStack();
TStack initTStack(){
	TStack TS = (TStack)malloc(sizeof(struct TreeList));
	TS->Tree = NULL;
	TS->Next = NULL;
}

void TStackPush(TStack TS, BinTree Tree);
void TStackPush(TStack TS, BinTree Tree){   //堆栈存和取都是对第一个进行操作
	TStack S = (TStack)malloc(sizeof(struct TreeList));
	S->Tree = Tree;
	S->Next = TS->Next;
	TS->Next = S;
}

BinTree TStackGet(TStack TS);
BinTree TStackGet(TStack TS){   //堆栈存和取都是对第一个进行操作
	TStack S = TS->Next;
	BinTree BT = S->Tree;
	TS->Next = TS->Next->Next;
	//printf("%d ", S->Tree->Data);    //最好这个时候不要print
	free(S);
	return BT;
}


//================================================
//队列的操作
typedef struct TreeQueue * TQueue;
struct TreeQueue{
	TList First;
	TList Last;
};

TQueue initTQueue();
TQueue initTQueue(){
	TQueue TQ = (TQueue)malloc(sizeof(struct TreeQueue));
	TQ->First = NULL;
	TQ->Last = NULL;
}

void TQueuePush(TQueue TQ, BinTree BT);
void TQueuePush(TQueue TQ, BinTree BT){
	TList TL = (TList)malloc(sizeof(struct TreeList));
	TL->Tree = BT;
	TL->Next = NULL;
	if (TQ->First != NULL) //如果TQ不为空
	{
		TQ->Last->Next = TL;
		TQ->Last = TL;
	}
	else      //TQ为空
	{
		TQ->First = TL;
		TQ->Last = TL;   //还不清楚能不能这样赋值
	}
}

TList TQueueGet(TQueue TQ);
TList TQueueGet(TQueue TQ){
	if (TQ->First != NULL){
		printf("%d ", TQ->First->Tree->Data);
		TList T = TQ->First;
		TQ->First = TQ->First->Next;
		return T;
	}
}


//==========================================================================
//树的遍历
void PreOrderTraversal(BinTree BT);		//先序----根、左子树、右子树；  
void InOrderTraversal(BinTree BT);		//中序-- - 左子树、根、右子树；  
void PostOrderTraversal(BinTree BT);	//后序-- - 左子树、右子树、根  
void LevelOrderTraversal(BinTree BT);	//层次遍历，从上到下、从左到右
//==========================================================================

void PreOrderTraversal(BinTree BT){
	if (BT)
	{
		printf("%d ", BT->Data);
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
	}
}

void InOrderTraversal(BinTree BT){
	if (BT)
	{
		InOrderTraversal(BT->Left);
		printf("%d ", BT->Data);
		InOrderTraversal(BT->Right);
	}
}

void PostOrderTraversal(BinTree BT){
	if (BT)
	{
		PostOrderTraversal(BT->Left);
		PostOrderTraversal(BT->Right);
		printf("%d ", BT->Data);
	}
}

void LevelOrderTraversal(BinTree BT){
	//需要用到队列
	TQueue TQ = initTQueue();
	if (BT)
	{
		TQueuePush(TQ, BT);
		while (TQ->First != NULL)
		{
			TList T = TQueueGet(TQ);
			if (T->Tree->Left)
			{
				TQueuePush(TQ, T->Tree->Left);
			}
			if (T->Tree->Right)
			{
				TQueuePush(TQ, T->Tree->Right);
			}
		}
	}
}

//======================================
//非递归方式-前序遍历
void PreOrderTraversal_02(BinTree BT);
void PreOrderTraversal_02(BinTree BT){
	TStack TS = initTStack();
	BinTree T = BT;
	while (TS->Next != NULL || T){
		while (T){
			TStackPush(TS, T);
			printf("%d ", T->Data);
			T = T->Left;
		}
		if (TS->Next != NULL){
			T = TStackGet(TS);
			T = T->Right;
		}
	}
}

//非递归方式-中序遍历
void InOrderTraversal_02(BinTree BT);
void InOrderTraversal_02(BinTree BT){
	TStack TS = initTStack();
	BinTree T = BT;
	while (TS->Next != NULL || T)
	{
		while (T)
		{
			TStackPush(TS, T);
			T = T->Left;
		}
		if (TS->Next != NULL)
		{
			T = TStackGet(TS);
			printf("%d ", T->Data);
			T = T->Right;
		}
	}
}

//非递归方式-后序遍历
void PostOrderTraversal_02(BinTree BT);
void PostOrderTraversal_02(BinTree BT){
	TStack TS = initTStack();			//从右往左遍历，刚好是右序便利倒过来
	TStack TS_02 = initTStack();
	BinTree T = BT;
	BinTree TT;
	while (TS->Next != NULL || T){
		while (T){
			TStackPush(TS, T);
			TStackPush(TS_02, T);    //把倒着的元素依次填入第二个堆栈
			T = T->Right;
		}
		if (TS->Next != NULL){
			T = TStackGet(TS);
			T = T->Left;
		}
	}
	while (TS_02->Next != NULL){   //把第二个堆栈输出就是正序的了
		TT = TStackGet(TS_02);
		printf("%d ", TT->Data);
	}
}


//===============================
//二叉搜索树 插入
BinTree BTInsert(BinTree BT, ElementType X);
BinTree BTInsert(BinTree BT, ElementType X){
	if (!BT)
	{
		BT = (BinTree)malloc(sizeof(struct TNode));
		BT->Data = X;
		BT->Left = BT->Right = NULL;
	}
	else
	{
		if (X < BT->Data)
		{
			BT->Left = BTInsert(BT->Left, X);
		}
		else if (X > BT->Data)
		{
			BT->Right = BTInsert(BT->Right, X);
		}
	}
	return BT;				//返回的依旧是最原始的根节点    递归里面，返回的也是每次递归参与的的根节点
}

//二叉搜索树  查找
BinTree BTFind(BinTree BT, ElementType X);
BinTree BTFind(BinTree BT, ElementType X){
	if (!BT){
		return NULL;   //直接return  而没有返回值的话，返回的不是null
	}
	if (X < BT->Data){
		return BTFind(BT->Left, X);
	}
	else if (X > BT->Data){
		return BTFind(BT->Right, X);
	}
	else{
		return BT;
	}
}

BinTree BTFind_02(BinTree BT, ElementType X);
BinTree BTFind_02(BinTree BT, ElementType X){
	//BinTree T = BT;
	while (BT)			//这个方法里面对BT的操作，似乎不会对真实的BT产生影响
	{
		if (X < BT->Data) BT = BT->Left;
		else if (X > BT->Data) BT = BT->Right;
		else return BT;
	}
	return NULL;
}

BinTree BTFindMax(BinTree BT);   //二叉搜索树中最大值在最右端，最小值在最左端
BinTree BTFindMax(BinTree BT){
	while (BT->Right)
	{
		BT = BT->Right;
	}
	return BT;
}

BinTree BTFindMin(BinTree BT);   //二叉搜索树中最大值在最右端，最小值在最左端
BinTree BTFindMin(BinTree BT){
	while (BT->Left)
	{
		BT = BT->Left;
	}
	return BT;
}

BinTree  BTDelete(BinTree BT, ElementType X);
BinTree  BTDelete(BinTree BT, ElementType X){
	BinTree T;
	if (X < BT->Data){
		BT->Left = BTDelete(BT->Left, X);
	}
	else if (X > BT->Data){
		BT->Right = BTDelete(BT->Right, X);
	}
	else{
		if (BT->Left && BT->Right){
			T = BTFindMax(BT->Left);
			BT->Data = T->Data;
			BT->Left = BTDelete(BT->Left, BT->Data);
		}else{

			//-----------------------------------------------------------------------------------
			//这里的才是递归的精髓，把进来的BT就看成只有一个节点或者单子树节点，需要删除的就是BT这个节点
			T = BT;					//T是要删除的节点
			if (!BT->Left){
				BT = BT->Right;    //左节点没有，如果有右节点就返回右节点，没有就返回null，
			}
			else if (!BT->Right){
				BT = BT->Left;
			}
			free(T);
			//-----------------------------------------------------------------------------------
		}
	}
	return BT;
}


#endif